
public class DuplicateSubstring
{

   /**
    * @param args
    */
   public static String longestDuplicate(String s) throws Exception
   {
      //String s = "again and again";
      //String s = "seven saints and seven dinners";
      //String s = "This is a cold, cold day; That was bad.";
      //String s = "Seven saints and seven sinners";
      //String s = "Mary had a little lamb";
      //String s = "racecaracecar";
      //String s = "BBBAAACBBBDAAAEBBB";
      
      char array[] = s.toCharArray();
      String current = "";
      String result = "";
      
      for(int i=0;i<s.length();i++)
      {
         for(int j=i+1;j<s.length();j++)
         {
               if(array[i] == array[j])
               {
                  for(int k=0;i+k<s.length() && j+k<s.length();k++)
                  {
                     if(i+k == j)
                     {
                        break;
                     }
                     else if(array[i+k] == array[j+k])
                     {
                        current+=array[i+k];    
                     }
                     else
                     {
                        break;
                     }
  
                  }
               }
               if(result.length()==0 || (result.length()<current.length()))
               {
                  result = current;
               }
               else if(result.length() == current.length() && result.charAt(0) > current.charAt(0))
               {
                  result = current;
               }
               
               current = "";
         }

         
      }
      //System.out.println(result);
      return result;
        
   }

}
